package binaryTree;

import java.util.ArrayList;
import java.util.List;

class Class98 {
//    // 递归
//    TreeNode max;
//    public boolean isValidBST(TreeNode root) {
//        if (root == null) {
//            return true;
//        }
//        // 左
//        boolean left = isValidBST(root.left);
//        if (!left) {
//            return false;
//        }
//        // 中
//        if (max != null && root.val <= max.val) {
//            return false;
//        }
//        max = root;
//        // 右
//        boolean right = isValidBST(root.right);
//        return right;
//    }

    boolean res=true;
    List<Integer> list=new ArrayList<Integer>();
    public boolean isValidBST(TreeNode root) {
//        使用中序遍历　　　遍历结果确定是否为一个单调递增数列　若是　则该树就是一个二叉搜索树木
        if (root == null) {
            return true;
        }
        list.add(Integer.MIN_VALUE);
        traverse(root);
        return res;
    }



    public void traverse(TreeNode  root){
        if (root==null){
            return;
        }
        traverse(root.left);
        if (root.val<=list.get(list.size()-1)){
            res=false;
        }
        list.add(root.val);
        traverse(root.right);
    }


    //todo:labuladong的方法　比较玄
    public boolean isValidBST1(TreeNode root) {
        return  isValidBST(root,null,null);
    }

    boolean isValidBST(TreeNode root,TreeNode min,TreeNode max){
        if (root==null){
            return  true;
        }
        if (min!=null&&root.val<=min.val){
            return  false;
        }
        if (max!=null&&root.val>=max.val)  {
            return  false;
        }
        return isValidBST(root.left,min,root)&&isValidBST(root.right,root,max);

    }


//  CKG TODO 2023/4/1: 学习

    public boolean isValidBST2(TreeNode root) {
        if (root == null || root.left == null && root.right == null) {
            return true;
        }
        //左子树是否合法
        if (isValidBST2(root.left)) {
            if (root.left != null) {
                int max = getMaxOfBST(root.left);//得到左子树中最大的数
                if (root.val <= max) { //相等的情况，代表有重复的数字
                    return false;
                }
            }

        }
        else {
            return false;
        }

        //右子树是否合法
        if (isValidBST2(root.right)) {
            if (root.right != null) {
                int min = getMinOfBST(root.right);//得到右子树中最小的数
                if (root.val >= min) { //相等的情况，代表有重复的数字
                    return false;
                }
            }

        }
        else {
            return false;
        }
        return true;
    }

    private int getMinOfBST(TreeNode root) {
        int min = root.val;
        while (root != null) {
            if (root.val <= min) {
                min = root.val;
            }
            root = root.left;
        }
        return min;
    }

    private int getMaxOfBST(TreeNode root) {
        int max = root.val;
        while (root != null) {
            if (root.val >= max) {
                max = root.val;
            }
            root = root.right;
        }
        return max;
    }




    public boolean isValidBST3(TreeNode root) {
        return getAns(root, null, null);
    }


    private boolean getAns(TreeNode node, Integer minValue, Integer maxValue) {
        if (node == null) {
            return true;
        }
        if (minValue != null && node.val <= minValue) {
            return false;
        }
        if (maxValue != null && node.val >= maxValue) {
            return false;
        }
        return getAns(node.left, minValue, node.val) && getAns(node.right, node.val, maxValue);
    }




    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        treeNode2.left=treeNode1;
        treeNode2.right=treeNode3;

        Class98 class98 = new Class98();
        boolean validBST = class98.isValidBST3(treeNode2);
        System.out.println(validBST);
    }
}
